package com.yiwenup.leetcode.hot;

import com.yiwenup.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
 **/
public class No0114 {

    private TreeNode pre = null;

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：41.3 MB, 在所有 Java 提交中击败了5.16%的用户
     */
    public void flatten3(TreeNode root) {
        if (root == null) return;

        flatten3(root.right);
        flatten3(root.left);

        root.right = pre;
        root.left = null;
        pre = root;
    }

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了30.74%的用户
     * 内存消耗：41 MB, 在所有 Java 提交中击败了15.71%的用户
     */
    public void flatten2(TreeNode root) {
        if (root == null) return;

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        TreeNode pre = null;
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            if (pre != null) {
                pre.left = null;
                pre.right = cur;
            }
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }

            pre = cur;
        }
    }

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了30.74%的用户
     * 内存消耗：41.2 MB, 在所有 Java 提交中击败了5.92%的用户
     */
    public void flatten1(TreeNode root) {

        List<TreeNode> list = new ArrayList<>();

        preOrder(root, list);

        for (int i = 1; i < list.size(); i++) {
            TreeNode pre = list.get(i - 1);
            TreeNode cur = list.get(i);
            pre.left = null;
            pre.right = cur;
        }
    }

    private void preOrder(TreeNode root, List<TreeNode> list) {
        if (root == null) return;
        list.add(root);
        preOrder(root.left, list);
        preOrder(root.right, list);
    }
}
